/*1802. 有界数组中指定下标处的最大值 */
/* https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/submissions/570887171/ */
/* 时间：10/9 难度：中等*/
/* 二分搜索 */
代码：
class Solution
{
private:
    long getsum(int x) { return (long)x * (x + 1) / 2; }

private:
    bool check(int h, int index, int n, long maxSum)
    {
        long sum = 0;
        if (h - (n - 1 - index) >= 1)
        {
            sum = (long)(n - index) * h - getsum(n - 1 - index);
        }
        else
        {
            sum += getsum(h) + n - index - h;
        }
        if (h - index >= 1)
        {
            sum += (long)index * h - getsum(index);
        }
        else
        {
            sum += getsum(h - 1) + index - h + 1;
        }
        return sum <= maxSum;
    }

public:
    int maxValue(int n, int index, int maxSum)
    {
        int l = 1, r = maxSum;
        while (l < r)
        {
            int mid = (l + r + 1) / 2;
            if (check(mid, index, n, maxSum))
            {
                l = mid;
            }
            else
                r = mid - 1;
        }
        return l;
    }
};